/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC rc;
    if ((rc = pf.open(indexname, mode )) < 0) return rc;
    if (pf.endPid() != 0)
    {
        BTreeIndexMemberVariables vars;
        pf.read(0, &vars);
        rootPid = vars.rootPid;
        treeHeight = vars.treeHeight;
    }
    else
    {
        // ensure that the first pid is saved for variables
        char filler[PageFile::PAGE_SIZE] = {0};
        if ((rc = pf.write(0, &filler)) < 0) return rc; 
    }

    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    RC rc;
    BTreeIndexMemberVariables vars;
    vars.rootPid = rootPid;
    vars.treeHeight = treeHeight;
    if ((rc = pf.write(0, &vars)) < 0) return rc;
    pf.close();
    return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
/*
    1   Perform search to leaf node
    2   If the bucket is not full, add the record.
    3   Otherwise, split the bucket.
    4       Allocate new leaf and move half the bucket's elements to the new bucket.
    5       Insert the new leaf's smallest key and address into the parent.
    6       If the parent is full, split it too.
    7           Add the middle key to the parent node.
    8       Repeat until a parent is found that need not split.
    9   If the root splits, create a new root which has one key and two pointers.
 */

RC BTreeIndex::insert(int key, const RecordId& rid)
{
    RC rc;
    bool insert = false;
    int getKey;
    BTLeafNode rootNode;
    PageId getPid;

    if (rootPid == -1)
    {
        rootPid = pf.endPid();
        BTLeafNode leaf;
        if ((rc = leaf.insert(key, rid)) < 0) return rc;
        if ((rc = leaf.write(rootPid, pf)) < 0) return rc;
    }
    else if (treeHeight == 0)
    {
        if ((rc = insertToLeafRoot(key, rid)) < 0) return rc;
    }
    else
    {
        if ((rc = insertHelper(rootPid, key, rid, insert, getKey, getPid)) < 0) return rc;

        if (insert)
        {
            if ((rc = insertToNonLeafRoot(getKey, getPid)) < 0) return rc;
        }
    }
    return 0;
}
// NON LEAF CODE
RC BTreeIndex::insertToNonLeafRoot(int key, const PageId& pid)
{

    RC rc;
    BTNonLeafNode newRoot;
    if ((rc = newRoot.initializeRoot(rootPid, key, pid)) < 0) return rc; 
    rootPid = pf.endPid();
    if ((rc = newRoot.write(rootPid, pf)) < 0) return rc;
    treeHeight++;
    return 0;
}
 /*
RC BTreeIndex::insertToNonLeafRoot(int key, const PageId& pid)
{
    cout << "inside insertToNonLeafRoot( " << key << ", " << pid << ") "  << endl;
    RC rc;
    int midKey;
    PageId endPid;
    BTNonLeafNode sibling;
    BTNonLeafNode rootNode;

    if ((rc = rootNode.read(rootPid, pf)) < 0) return rc;
    cout << "inserting " << key << " to rootPid " << rootPid << endl;
    rc = rootNode.insert(key, pid);
    // split root: 9
    if (rc == RC_NODE_FULL)
    {
        cout << "ROOT IS FULL" << endl;
        cout << "full node, splitting with key " << key << " pid " << pid << endl;
        if ((rc = rootNode.insertAndSplit(key, pid, sibling, midKey)) < 0) return rc;
        if ((rc = rootNode.write(rootPid, pf)) < 0) return rc;

        endPid = pf.endPid();
        if ((rc = sibling.write(endPid, pf)) < 0) return rc;

        BTNonLeafNode newRoot;
        cout << "initializingRoot with pid " << rootPid << " key (midKey) : " << midKey << " pid: " << endPid;
        if ((rc = newRoot.initializeRoot(rootPid, midKey, endPid)) < 0) return rc; 

        rootPid = pf.endPid();
        if ((rc = newRoot.write(rootPid, pf)) < 0) return rc;

        cout << "tree height incrased by one" << endl;
        treeHeight++;
    }
    else
        if ((rc = rootNode.write(rootPid, pf)) < 0) return rc;
    return 0;
}
*/
RC BTreeIndex::insertToLeafRoot(int key, const RecordId& rid)
{
    RC rc;
    int midKey;
    PageId endPid;
    BTLeafNode sibling;
    BTLeafNode rootNode;

    if ((rc = rootNode.read(rootPid, pf)) < 0) return rc;
    rc = rootNode.insert(key, rid);
    // split root: 9
    if (rc == RC_NODE_FULL)
    {

        if ((rc = insertAndSplitWriteLeaf(rootNode, rootPid, key, rid, sibling, midKey, endPid)) < 0) return rc;

        BTNonLeafNode newRoot;
        if ((rc = newRoot.initializeRoot(rootPid, midKey, endPid)) < 0) return rc; 

        rootPid = pf.endPid();
        if ((rc = newRoot.write(rootPid, pf)) < 0) return rc;

        treeHeight++;
    }
    else
        if ((rc = rootNode.write(rootPid, pf)) < 0) return rc;
    return 0;
}
RC BTreeIndex::insertHelper(PageId pid, int key, const RecordId& rid, bool &resultInsert, int& resultKey, PageId& resultPid)
{
    RC rc;
    bool insert = false;
    int addKey;
    int midKey;
    BTNonLeafNode sibling;
    BTLeafNode leafSibling;
    PageId endPid;
    PageId getPid;
    PageId addPid;


    NonLeafNodeContents node;
    pf.read(pid, &node);

    if (node.indicator == LEAF_NODE)
    {
        BTLeafNode leafNode;
        leafNode.read(pid, pf);
        
        rc = leafNode.insert(key, rid);

        if (rc == RC_NODE_FULL)
        {
            if ((rc = insertAndSplitWriteLeaf(leafNode, pid, key, rid, leafSibling, midKey, endPid)) < 0) return rc;
            resultInsert = true;
            resultKey = midKey;
            resultPid = endPid;
        }
        else if (rc < 0)
        {
            return rc;
        }
        else
            if ((rc = leafNode.write(pid, pf)) < 0) return rc;
    }
    else
    {

        // NON LEAF CODE
        BTNonLeafNode nonLeafNode;
        nonLeafNode.read(pid, pf);

        if ((rc = nonLeafNode.locateChildPtr(key, getPid)) < 0) return rc;
        if ((rc = insertHelper(getPid, key, rid, insert, addKey, addPid)) < 0) return rc;
        if (insert)
        {
            rc = nonLeafNode.insert(addKey, addPid);
            if (rc == RC_NODE_FULL)
            {
                endPid = pf.endPid();
                if ((rc = nonLeafNode.insertAndSplit(addKey, addPid, sibling, midKey)) < 0) return rc;
                if ((rc = nonLeafNode.write(pid, pf)) < 0) return rc;

                if ((rc = sibling.write(endPid, pf)) < 0) return rc;
                resultInsert = true;
                resultKey = midKey;
                resultPid = endPid;
            }
            else if (rc < 0)
            {
                return rc;
            }
            else 
                if ((rc = nonLeafNode.write(pid, pf)) < 0) return rc;

            
        }
    }
    return 0;
}
RC BTreeIndex::insertAndSplitWriteLeaf(BTLeafNode leafNode, PageId leafNodePid, int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey, PageId& resultEndPid)
{
    RC rc;
    PageId endPid = pf.endPid();
    resultEndPid = endPid;
    if ((rc = leafNode.insertAndSplit(key, rid, sibling, endPid, siblingKey)) < 0) return rc;
    if ((rc = leafNode.write(leafNodePid, pf)) < 0) return rc;
    if ((rc = sibling.write(endPid, pf)) < 0) return rc;
    return 0;
}
/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    RC rc;
    int eidFound;
    
    if (rootPid == -1) //If it is an empty tree
        return RC_NO_SUCH_RECORD;
    
    if (treeHeight == 0)
    {
        BTLeafNode currentNode;
        if ((rc = currentNode.read(rootPid, pf)) < 0) return rc;
        if ((rc = currentNode.locate(searchKey, eidFound)) < 0) return rc;
        cursor.eid = eidFound;
        cursor.pid = rootPid;
        return 0;
    }
    
    BTNonLeafNode currentNonLeafNode;
    int currentPid = rootPid;
    
    for (int i = 1; i <= treeHeight; i++)
    {
        if ((rc = currentNonLeafNode.read(currentPid, pf)) < 0) return rc;
        currentNonLeafNode.locateChildPtr(searchKey, currentPid);
    }
    
    BTLeafNode finalLeafNode;
    if ((rc = finalLeafNode.read(currentPid, pf)) < 0) return rc;
    if ((rc = finalLeafNode.locate(searchKey, eidFound)) < 0) return rc;
    
    cursor.pid = currentPid;
    cursor.eid = eidFound;
    
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    RC rc;
    BTLeafNode finalLeafNode;
    if ((rc = finalLeafNode.read(cursor.pid, pf)) < 0) return rc;
    if ((rc = finalLeafNode.readEntry(cursor.eid, key, rid)) < 0) return rc;
    if ((cursor.eid + 1) < finalLeafNode.getKeyCount()) cursor.eid++;
    else
    {
        if((cursor.pid = finalLeafNode.getNextNodePtr()) == 0) return RC_END_OF_TREE;
        cursor.eid = 0;
    }
    return 0;
}
